1584. Произвольное тасование

Произвольное тасование чисел массива А производится согласно следующего алгоритма:

n = длина массива А

for i=1 to n

сгенерировать произвольное число r между 1 и n включительно

поменять местами A[i] и A[r]

Вычислить вероятность того, что заданный массив чисел получен в результате выполнения операции произвольного тасования набора {1, 2, …, n}. Здесь n равно количеству элементов входного массива.

Вход. Каждая строка является отдельным тестом и содержит значение n (1 ≤ n ≤ 10), за которым следуют элементы массива А – перестановка чисел от 1 до n.

Выход. Для каждого теста в отдельной строке вывести с 4 цифрами после десятичной точки вероятность того, что входной массив получен в результате выполнения операции произвольного тасования набора {1, 2, …, n}.

Пример входа

1 1

2 1 2

5 4 2 5 1 3

Пример выхода

1.0000

0.5000

0.0067

РЕШЕНИЕ

вероятность - рекурсия - перебор

Анализ алгоритма

Занесем в массив cur последовательность {1, 2, …, n}. Будем моделировать все возможные процессы тасования, выбирая в качестве значения r все значения от 1 до n. Процесс тасования состоит из n итераций, на каждой из которых в качестве r можно выбрать любое из n чисел (от 1 до n). Таким образом, из последовательности {1, 2, …, n} в результате тасования можно получить nⁿ других последовательностей, некоторые из которых возможно будут одинаковыми (nⁿ > n!). В переменной s подсчитаем, сколько раз в процессе моделирования из {1, 2, …, n} получится последовательность, заданная в массиве outputArray. Разделив найденное число s на nⁿ, получим искомую вероятность.

Функция shuffle имеет единственный параметр pos – номер проводимой итерации. Для прохождения по времени следует совершить следующее отсечение. Пусть производится pos итерация, а текущий массив cur отличается от исходного m в c позициях. Тогда если c > 2*(n –pos), то очевидно, что за оставшиеся n – pos обменов невозможно из cur получить m. Это следует из того, что за каждый из оставшихся обменов мы можем переставлять максимум 2 элемента.

Реализация алгоритма

Объявим глобальные массивы.

int m[10], cur[10];

Реализация функции произвольного тасования.

void shuffle(int pos)

{

int i, c;

if (pos == n)

{

for(i = 0; i < n; i++)

if (m[i] != cur[i]) return;

s++;

return;

}

for(c = i = 0; i < n; i++)

if (m[i] != cur[i]) c++;

if (c > 2 * (n - pos)) return;

for(i = 0; i < n; i++)

{

swap(cur[i],cur[pos]);

shuffle(pos + 1);

swap(cur[i],cur[pos]);

}

}

Основная часть программы.

while(scanf("%d",&n) == 1)

{

for(s = i = 0; i < n; i++)

scanf("%d",&m[i]), cur[i] = i + 1;

shuffle(0);

res = 1.0 * s / pow((double)n,(double)n);

printf("%.4lf\n",res);

}